package com.bitauto.i.commonUtils.leet;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 给定一个字符串，找到没有重复字符的最长子串，返回它的长度。
 */
public class Answer3 {

    public static void main(String[] args) {
        //String s ="skgefasdf";
        String s ="bbbbb";
        int length=lengthOfLongestSubstring1(s);
        System.out.println(length);

        int length2=lengthOfLongestSubstring2(s);
        System.out.println(length2);

        int length3=lengthOfLongestSubstring3(s);
        System.out.println(length3);
    }

    /**
     * 这种时间复杂度最高，不推荐
     * @param s
     * @return
     */
    private static int lengthOfLongestSubstring1(String s) {
        int n = s.length();
        int ans = 0;//保存当前得到满足条件的子串的最大值
        for(int i=0;i<n;i++){
            for (int j=i+1;j<=n;j++){
                if(allUniqe(s,i,j)){
                    ans = Math.max(ans, j - i);
                }
            }
        }
        return ans;
    }

    private static boolean allUniqe(String s, int start, int end) {
        Set<Character> set= new HashSet<Character>();
        for (int i=start;i<end;i++){
            Character ch = s.charAt(i);
            if(set.contains(ch)){
                return false;
            }else{
                set.add(ch);
            }
        }
        return true;
    }


    /**
     * 有点划片那意思，但是会有无效划的步骤，还能优化
     * @param s
     * @return
     */
    private static int lengthOfLongestSubstring2(String s) {
        Set<Character> set= new HashSet<Character>();
        int ans = 0;//保存当前得到满足条件的子串的最大值
        int n=s.length();
        int i=0,j=0;
        while (i<n && j<n){
            if (!set.contains(s.charAt(j))) {
                Character ss=s.charAt(j++);
                set.add(ss);
                ans=Math.max(ans,j-i);
                //j++;
            }else{
                set.remove(s.charAt(i));
                i++;
            }
        }
        return ans;
    }

    private static int lengthOfLongestSubstring3(String s) {
        //skgefasdf
        Map<Character,Integer> map= new HashMap<Character,Integer>();
        int ans = 0;//保存当前得到满足条件的子串的最大值
        int n=s.length();
        int i=0;
        for (int j=0;j<n;j++){
            Character ss=s.charAt(j);
            if(map.containsKey(ss)){
                i=Math.max(map.get(s.charAt(j)),i);
            }else{
                ans=Math.max(j-i+1,ans);
            }
            //下标 + 1 代表 i 要移动的下个位置
            map.put(s.charAt(j),j+1);
        }
        return ans;
    }

}
